type Node struct {
    // 每个节点包含：
    // 1. 一个字符
    // 2. 若干个子节点
    // a-z 26 个字符
    // a -> 0, b -> 1.... z -> 26
    // a - a = 0
    // b - a = 1
    children [26]*Node
    // 标识，这个节点是否是一个单词最后一个字符
    isWord bool
}

func newNode() *Node {
    return &Node{children:[26]*Node{}, isWord:false}
}

type WordDictionary struct {
    root *Node
}


func Constructor() WordDictionary {
    return WordDictionary{root:newNode()}
}


func (this *WordDictionary) AddWord(word string)  {
    var curr = this.root
    for i := range word {
        var c = word[i]
        // 1. 先从子节点中查找是否包含当前字符 c
        if curr.children[c - 'a'] == nil {
            curr.children[c - 'a'] = newNode()
        }
        curr = curr.children[c - 'a'] 
    }
    curr.isWord = true
}


func (this *WordDictionary) Search(word string) bool {

    var dfs func(*Node, int) bool
    dfs = func(node *Node, index int) bool {
        if index == len(word) {
            return node.isWord;
        }
        c := word[index]
        if c != '.' {
            if node.children[c - 'a'] == nil {
                return false
            }
            return dfs(node.children[c - 'a'], index + 1)
        } else {
            for i := range node.children {
                child := node.children[i]
                if child != nil && dfs(child, index + 1) {
                    return true
                }
            }
            return false
        }
    }

    return dfs(this.root, 0)
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */